

def bubble_sort(arr):
    """
    冒泡排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    
    Args:
        arr: 待排序的列表
    
    Returns:
        排序后的列表
    """
    n = len(arr)
    
    # 外层循环控制排序轮数
    for i in range(n):
        # 优化：设置标志位检测是否已经排序完成
        swapped = False
        
        # 内层循环进行相邻元素比较和交换
        # 每轮排序后，最大的元素会"冒泡"到末尾
        for j in range(0, n - i - 1):
            # 如果前面的元素大于后面的元素，则交换
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果这一轮没有发生交换，说明数组已经有序
        if not swapped:
            break
    
    return arr


def bubble_sort_demo():
    """冒泡排序演示函数"""
    print("=== 冒泡排序演示 ===")
    
    # 测试用例1：随机数组
    test_arr1 = [64, 34, 25, 12, 22, 11, 90]
    print(f"原始数组: {test_arr1}")
    sorted_arr1 = bubble_sort(test_arr1.copy())
    print(f"排序后:   {sorted_arr1}")
    print()
    
    # 测试用例2：已排序数组
    test_arr2 = [1, 2, 3, 4, 5]
    print(f"已排序数组: {test_arr2}")
    sorted_arr2 = bubble_sort(test_arr2.copy())
    print(f"排序后:     {sorted_arr2}")
    print()
    
    # 测试用例3：逆序数组
    test_arr3 = [5, 4, 3, 2, 1]
    print(f"逆序数组: {test_arr3}")
    sorted_arr3 = bubble_sort(test_arr3.copy())
    print(f"排序后:   {sorted_arr3}")
    print()
    
    # 测试用例4：包含重复元素
    test_arr4 = [3, 7, 3, 8, 1, 7, 3]
    print(f"包含重复元素: {test_arr4}")
    sorted_arr4 = bubble_sort(test_arr4.copy())
    print(f"排序后:       {sorted_arr4}")


def bubble_sort_with_steps(arr):
    """
    带详细步骤显示的冒泡排序
    用于教学演示
    """
    print(f"开始排序: {arr}")
    n = len(arr)
    
    for i in range(n):
        print(f"\n第 {i + 1} 轮排序:")
        swapped = False
        
        for j in range(0, n - i - 1):
            print(f"  比较 {arr[j]} 和 {arr[j + 1]}", end="")
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f" -> 交换: {arr}")
            else:
                print(f" -> 不交换: {arr}")
        
        if not swapped:
            print(f"  本轮无交换，排序完成！")
            break
            
        print(f"第 {i + 1} 轮结束: {arr}")
    
    print(f"\n最终结果: {arr}")
    return arr


if __name__ == "__main__":
    # 运行演示
    bubble_sort_demo()
    
    print("\n" + "="*50)
    print("详细步骤演示:")
    print("="*50)
    
    # 详细步骤演示
    demo_arr = [5, 2, 8, 1, 9]
    bubble_sort_with_steps(demo_arr.copy())

